/*
 * @lc app=leetcode.cn id=149 lang=cpp
 *
 * [149] 直线上最多的点数
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<int> calSlope(vector<int> p1, vector<int> p2)
    {
        int a = p2[1] - p1[1];
        int b = p2[0] - p1[0];
        int c = 0;
        if (a == 0)
        {
            b = 1;
        }
        else if (b == 0)
        {
            a = 1;
        }
        else
        {
            if (a < 0)
            {
                a = -a;
                b = -b;
            }
            int z = __gcd(a, b);
            a /= z;
            b /= z;
            c = -a * p1[0] - b * p1[1];
        }

        return {p1[0], p1[1], a, b, c};
    }
    int maxPoints(vector<vector<int>> &points)
    {
        if (points.size() < 3)
            return points.size();
        sort(points.begin(), points.end());
        //判断与y轴平行直线上有多少点
        int ans = 2; //至少会有两个点在同一条直线上
        map<vector<int>, set<vector<int>>> m;

        // for (int i = 0, j = 1; j < points.size(); i = j, j++)
        // {
        // while (j < points.size() && points[j][0] == points[i][0])
        //     j++;
        // ans = max(j - i, ans);

        // for (int h = i; h < j; h++)
        //     for (int k = j; k < points.size(); k++)
        //     {
        //         auto p = calSlope(points[h], points[k]);
        //         m[p].insert(points[k]);
        //     }

        // }

        for (int i = 0; i < points.size(); i++)
        {
            vector<int> tmp = points[i];
            for (int k = i + 1; k < points.size(); k++)
            {
                auto p = calSlope(tmp, points[k]);
                m[p].insert(points[k]);
            }
        }

        for (auto &it : m)
        {
            ans = max(ans, (int)it.second.size() + 1);
        }
        return ans;
    }
};

// int main()
// {
//     // vector<vector<int>> points = {
//     //     {0,0},{4,5},{7,8},{8,9},{5,6},{3,4},{1,1}
//     // };//5
//     vector<vector<int>> points = {
//         {7, 3}, {19, 19}, {-16, 3}, {13, 17}, {-18, 1}, {-18, -17}, {13, -3}, {3, 7}, {-11, 12}, {7, 19}, {19, -12}, {20, -18}, {-16, -15}, {-10, -15}, {-16, -18}, {-14, -1}, {18, 10}, {-13, 8}, {7, -5}, {-4, -9}, {-11, 2}, {-9, -9}, {-5, -16}, {10, 14}, {-3, 4}, {1, -20}, {2, 16}, {0, 14}, {-14, 5}, {15, -11}, {3, 11}, {11, -10}, {-1, -7}, {16, 7}, {1, -11}, {-8, -3}, {1, -6}, {19, 7}, {3, 6}, {-1, -2}, {7, -3}, {-6, -8}, {7, 1}, {-15, 12}, {-17, 9}, {19, -9}, {1, 0}, {9, -10}, {6, 20}, {-12, -4}, {-16, -17}, {14, 3}, {0, -1}, {-18, 9}, {-15, 15}, {-3, -15}, {-5, 20}, {15, -14}, {9, -17}, {10, -14}, {-7, -11}, {14, 9}, {1, -1}, {15, 12}, {-5, -1}, {-17, -5}, {15, -2}, {-12, 11}, {19, -18}, {8, 7}, {-5, -3}, {-17, -1}, {-18, 13}, {15, -3}, {4, 18}, {-14, -15}, {15, 8}, {-18, -12}, {-15, 19}, {-9, 16}, {-9, 14}, {-12, -14}, {-2, -20}, {-3, -13}, {10, -7}, {-2, -10}, {9, 10}, {-1, 7}, {-17, -6}, {-15, 20}, {5, -17}, {6, -6}, {-11, -8}}; // 6
//     cout << Solution().maxPoints(points) << endl;
//     return 0;
// }

// @lc code=end
